<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    916. Decoded String at Index
   </h1>
   <p>
    An encoded string
    <code>
     S
    </code>
    is given.&nbsp; To find and write the
    <em>
     decoded
    </em>
    string to a tape, the encoded string is read
    <strong>
     one character at a time
    </strong>
    &nbsp;and the following steps are taken:
   </p>
   <ul>
    <li>
     If the character read is a letter, that letter is written onto the tape.
    </li>
    <li>
     If the character read is a digit (say
     <code>
      d
     </code>
     ), the entire current tape is repeatedly written&nbsp;
     <code>
      d-1
     </code>
     &nbsp;more times in total.
    </li>
   </ul>
   <p>
    Now for some encoded string
    <code>
     S
    </code>
    , and an index
    <code>
     K
    </code>
    , find and return the
    <code>
     K
    </code>
    -th letter (1 indexed) in the decoded string.
   </p>
   <p>
    &nbsp;
   </p>
   <div>
    <p>
     <strong>
      Example 1:
     </strong>
    </p>
    <pre>
<strong>Input: </strong>S = <span id="example-input-1-1">"leet2code3"</span>, K = <span id="example-input-1-2">10</span>
<strong>Output: </strong><span id="example-output-1">"o"</span>
<strong>Explanation: </strong>
The decoded string is "leetleetcodeleetleetcodeleetleetcode".
The 10th letter in the string is "o".
</pre>
    <div>
     <p>
      <strong>
       Example 2:
      </strong>
     </p>
     <pre>
<strong>Input: </strong>S = <span id="example-input-2-1">"ha22"</span>, K = <span id="example-input-2-2">5</span>
<strong>Output: </strong><span id="example-output-2">"h"</span>
<strong>Explanation: </strong>
The decoded string is "hahahaha".  The 5th letter is "h".
</pre>
     <div>
      <p>
       <strong>
        Example 3:
       </strong>
      </p>
      <pre>
<strong>Input: </strong>S = <span id="example-input-3-1">"a2345678999999999999999"</span>, K = <span id="example-input-3-2">1</span>
<strong>Output: </strong><span id="example-output-3">"a"</span>
<strong>Explanation: </strong>
The decoded string is "a" repeated 8301530446056247680 times.  The 1st letter is "a".
</pre>
      <p>
       &nbsp;
      </p>
      <p>
       <strong>
        Note:
       </strong>
      </p>
      <ol>
       <li>
        <code>
         2 &lt;= S.length &lt;= 100
        </code>
       </li>
       <li>
        <code>
         S
        </code>
        &nbsp;will only contain lowercase letters and digits
        <code>
         2
        </code>
        through
        <code>
         9
        </code>
        .
       </li>
       <li>
        <code>
         S
        </code>
        &nbsp;starts with a letter.
       </li>
       <li>
        <code>
         1 &lt;= K &lt;= 10^9
        </code>
       </li>
       <li>
        The decoded string is guaranteed to have less than
        <code>
         2^63
        </code>
        letters.
       </li>
      </ol>
     </div>
    </div>
   </div>
  </div>
  <div>
   <h1 class="question_title">
    916. 索引处的解码字符串
   </h1>
   <p>
    给定一个编码字符串
    <code>
     S
    </code>
    。为了找出
    <em>
     解码
    </em>
    字符串并将其写入磁带，从编码字符串中
    <code>
     每次读取一个字符
    </code>
    ，并采取以下步骤：
   </p>
   <ul>
    <li>
     如果所读的字符是字母，则将该字母写在磁带上。
    </li>
    <li>
     如果所读的字符是数字（例如
     <code>
      d
     </code>
     ），则整个当前磁带总共会被重复写&nbsp;
     <code>
      d-1
     </code>
     次。
    </li>
   </ul>
   <p>
    现在，对于给定的编码字符串
    <code>
     S
    </code>
    和索引
    <code>
     K
    </code>
    ，查找并返回解码字符串中的第&nbsp;
    <code>
     K
    </code>
    &nbsp;个字母。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例 1：
    </strong>
   </p>
   <pre><strong>输入：</strong>S = "leet2code3", K = 10
<strong>输出：</strong>"o"
<strong>解释：</strong>
解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
字符串中的第 10 个字母是 "o"。
</pre>
   <p>
    <strong>
     示例 2：
    </strong>
   </p>
   <pre><strong>输入：</strong>S = "ha22", K = 5
<strong>输出：</strong>"h"
<strong>解释：</strong>
解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。
</pre>
   <p>
    <strong>
     示例 3：
    </strong>
   </p>
   <pre><strong>输入：</strong>S = "a2345678999999999999999", K = 1
<strong>输出：</strong>"a"
<strong>解释：</strong>
解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      2 &lt;= S.length &lt;= 100
     </code>
    </li>
    <li>
     <code>
      S
     </code>
     &nbsp;只包含小写字母与数字
     <code>
      2
     </code>
     到
     <code>
      9
     </code>
     。
    </li>
    <li>
     <code>
      S
     </code>
     &nbsp;以字母开头。
    </li>
    <li>
     <code>
      1 &lt;= K &lt;= 10^9
     </code>
    </li>
    <li>
     解码后的字符串保证少于&nbsp;
     <code>
      2^63
     </code>
     &nbsp;个字母。
    </li>
   </ol>
  </div>
 </body>
</html>